<html>
<head><meta charset="utf-8"><title>Salsa q · t-compiler/rust-analyzer · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/index.html">t-compiler/rust-analyzer</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html">Salsa q</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="196043755"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196043755" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196043755">(May 02 2020 at 09:50)</a>:</h4>
<p>I'm studying salsa -- in this line <a href="https://github.com/salsa-rs/salsa/blob/master/src/interned.rs#L272" title="https://github.com/salsa-rs/salsa/blob/master/src/interned.rs#L272">https://github.com/salsa-rs/salsa/blob/master/src/interned.rs#L272</a> how do we guarantee that <code>values.len()</code> won't be 0 ? It's initialized as an empty vector, so it seems to me that it's possible to get a <code>0</code> there, but that would break <code>InternId</code> (which can't be 0), so I'm wondering what I'm missing.</p>



<a name="196043807"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196043807" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196043807">(May 02 2020 at 09:52)</a>:</h4>
<p>we don't we +1 instead: <a href="https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L64" title="https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L64">https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L64</a></p>



<a name="196043825"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196043825" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196043825">(May 02 2020 at 09:53)</a>:</h4>
<p>Hmm but <code>tables.values.len()</code> is a <code>usize</code>, not <code>u32</code>, right?</p>



<a name="196043850"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196043850" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196043850">(May 02 2020 at 09:53)</a>:</h4>
<p>which goes via this impl: <a href="https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L112-L117" title="https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L112-L117">https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L112-L117</a></p>



<a name="196043853"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196043853" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196043853">(May 02 2020 at 09:53)</a>:</h4>
<p>I was expecting that we'd call this line <a href="https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L115" title="https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L115">https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L115</a></p>



<a name="196043898"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196043898" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196043898">(May 02 2020 at 09:54)</a>:</h4>
<p>Yes, we do, and <code>new_uncecked</code> does +1</p>



<a name="196043899"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196043899" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196043899">(May 02 2020 at 09:54)</a>:</h4>
<p>Ahh, I see. Thanks!</p>



<a name="196044471"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044471" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044471">(May 02 2020 at 10:08)</a>:</h4>
<p>Another related question, why is the max value of InterId defined as  <code>0xFFFF_FF00</code> instead of <code>std::u32::MAX</code> ?</p>



<a name="196044700"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044700" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044700">(May 02 2020 at 10:14)</a>:</h4>
<p>For future compatability</p>



<a name="196044712"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044712" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044712">(May 02 2020 at 10:14)</a>:</h4>
<p>Ideally, we want to use not the <code>NonZero</code>, but "highest two bits are zero"</p>



<a name="196044721"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044721" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044721">(May 02 2020 at 10:14)</a>:</h4>
<p>This is what rustc is using, and it is measurably faster</p>



<a name="196044732"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044732" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044732">(May 02 2020 at 10:15)</a>:</h4>
<p>but to do that, you need unstable API to specify valid patterns precisely</p>



<a name="196044809"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044809" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044809">(May 02 2020 at 10:17)</a>:</h4>
<p>Do you mean least significant bits? Why does that matter for performance?</p>



<a name="196044859"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044859" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044859">(May 02 2020 at 10:18)</a>:</h4>
<p>no, I mean highest</p>



<a name="196044870"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044870" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044870">(May 02 2020 at 10:19)</a>:</h4>
<p>with no-zero, you need to do <code>- 1</code> for every index access, which is not free</p>



<a name="196044879"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044879" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044879">(May 02 2020 at 10:19)</a>:</h4>
<p>with "highlest two bits are always zero", you don't need to do anything special for indexing, but you still have space for niche-filling</p>



<a name="196044955"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196044955" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196044955">(May 02 2020 at 10:20)</a>:</h4>
<p>Why does highest bits matter for <code>- 1</code> performance? What do you mean by "special"?</p>



<a name="196045027"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196045027" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196045027">(May 02 2020 at 10:22)</a>:</h4>
<p>two cases:</p>
<p>Case 1:</p>
<p>idx is a NonZeroU32 index. To access vector element, we need to do <code>xs[idx as usize - 1]</code> (we need -1, b/c we added one when creating the index)</p>
<p>Case 2:</p>
<p>idx is TwoHighestBitsAreZero index. To access vector element, we need to do <code>xs[idx as usize]</code></p>



<a name="196045199"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196045199" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196045199">(May 02 2020 at 10:26)</a>:</h4>
<p>Ahh, so same optimizations are applied to TwoHighestBitsAreZero (e.g. Option&lt;TwoHighestBitsAreZero&gt; has the same size as TwoHighestBitsAreZero) ?</p>



<a name="196045228"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196045228" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196045228">(May 02 2020 at 10:27)</a>:</h4>
<p>yup</p>



<a name="196045387"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196045387" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196045387">(May 02 2020 at 10:31)</a>:</h4>
<p>OK, but I still can't relate that to the max value chosen for InterId. Max value for TwoHighestBitsAreZero would be <code>0x3FFFFFFF</code>, I think</p>



<a name="196045501"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196045501" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196045501">(May 02 2020 at 10:34)</a>:</h4>
<p>riiight, I think this actually might be a bug?</p>



<a name="196045503"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196045503" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196045503">(May 02 2020 at 10:34)</a>:</h4>
<p>Or it might also be me not understanding things...</p>



<a name="196045932"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Salsa%20q/near/196045932" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Salsa.20q.html#196045932">(May 02 2020 at 10:45)</a>:</h4>
<p>OK, thanks for the answers. This has been educational to me. Another question: why does InternId implement From&lt;u32&gt; and From&lt;usize&gt;? That means users of salsa can invent InternIds out of thin air, which shouldn't be possible, I think. I'd expect to obtain InternIds <em>only</em> by interning.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>